package leetcode.editor.cn;

import java.util.Arrays;

/**
 * 最长重复子数组
 * @author qulq
 * @date 2024-07-28 10:21:16
 */
public class T718_MaximumLengthOfRepeatedSubarray{
	 public static void main(String[] args) {
	 	 // 测试代码
		 Solution solution = new T718_MaximumLengthOfRepeatedSubarray().new Solution();
		 System.out.println(solution.findLength(new int[]{0, 1, 1, 1, 1}, new int[]{1, 0, 1, 0, 1}));
	 }

	/**
	 * f[i][j] :A的前i个、B的前j个的最长....
	 * 因为是要求连续的，所以不用考虑f[i-1][j], f[i][j-1] 的情况
	 * f[i][j] = f[i-1][j-1] + 1 | Ai-1 = Bj-1
	 */

// 力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
		int[][] dp = new int[nums1.length + 1][nums2.length + 1];
		int ans = 0;
		for (int i = 0; i <= nums1.length; i++) {
			for (int j = 0; j <= nums2.length; j++) {
				if (i == 0 || j == 0) {
					dp[i][j] = 0;
					continue;
				}
				if (nums1[i - 1] == nums2[j - 1]) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
				}
				ans = Math.max(ans, dp[i][j]);
			}
		}
		return ans;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}